/**
 * 32. 最长有效括号
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 *
 * 示例 1：
 * 输入：s = "(()"
 * 输出：2
 * 解释：最长有效括号子串是 "()"
 *
 * 示例 2：
 * 输入：s = ")()())"
 * 输出：4
 * 解释：最长有效括号子串是 "()()"
 *
 * 示例 3：
 * 输入：s = ""
 * 输出：0
 *
 * 提示：
 * 0 <= s.length <= 3 * 104
 * s[i] 为 '(' 或 ')'
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

package zw;

import java.util.ArrayList;
import java.util.Stack;

class T32 {
    public static int longestValidParentheses(String s) {
        Stack<Character> stackChar = new Stack<>();
        Stack<Integer> stackIndex = new Stack<>();
        ArrayList<Integer> record = new ArrayList<>();
        ArrayList<Integer> record2 = new ArrayList<>();
        int f, e;
        int result;
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') {
                stackChar.add(s.charAt(i));
                stackIndex.add(i);
            } else if(!stackChar.empty()){
                stackChar.pop();
                record.add(stackIndex.pop());
                record.add(i);
            }
        }
        if(record.size() == 0) {
            return 0;
        }
        if(record.size() == 2) {
            return record.get(1)-record.get(0)+1;
        }
        f = record.get(record.size()-2);
        e = record.get(record.size()-1);
        record2.add(f);
        record2.add(e);
        for(int i = record.size() - 4; i >= 0; i -= 2) {
            if(!(record.get(i) > f && record.get(i+1) < e)) {
                f = record.get(i);
                e = record.get(i + 1);
                record2.add(f);
                record2.add(e);
            }
        }
        if(record2.size()==2){
            return record2.get(1) - record2.get(0) + 1;
        }
        f = record2.get(0);
        e = record2.get(1);
        result = e-f+1;
        for(int i = 2; i <= record2.size()-1; i+=2) {
            if(record2.get(i+1) + 1 == f) {
                f = record2.get(i);
                if(result < (e-f+1)) {
                    result = e-f+1;
                }
            } else {
                f = record2.get(i);
                e = record2.get(i+1);
                if(result <= e-f+1) {
                    result = e-f+1;
                }
            }
        }
        return result;
    }


    // 动态规划
    public static int longestValidParentheses2(String s) {
        int[] dp = new int[s.length()];
        int result = 0;
        for(int i = 1; i < s.length(); i++) {
            if(s.charAt(i) == ')') {
                if(s.charAt(i-1) == '(') {
                    if(i < 2) {
                        dp[i] = 2;
                    } else {
                        dp[i] = dp[i-2] + 2;
                    }
                    result = Math.max(result, dp[i]);
                } else if((i - dp[i-1] > 0) && s.charAt(i - dp[i-1] - 1) == '(') {
                    int a = (i - dp[i-1]-2) >= 0 ? dp[i - dp[i-1]-2] : 0;
                    dp[i] = a + dp[i-1] + 2;
                    result = Math.max(result, dp[i]);
                }
            }
        }
        return result;
    }
}
